Forward security refers to a cryptographic property according to which an exposed secret key can affect the security of the underlying system only in the future but not in the past. Forward security is often implemented through systematic pseudorandom key updates, so that the usage of older keys in the past remains secure indefinitely in the future, despite any possible compromises of newer keys that may occur in the future. However, this key-update procedure introduces additional computational and storage overheads, especially for applications where keys must be updated asynchronously or on demand, i.e., a new key that is “distant” from the current key must be produced, thus the key-update procedure must operate in a “jump-ahead” fashion (for example, from a prior month to a current minute).
U.S. patent application Ser. No. 13/334,709, entitled “Methods and Apparatus for Generating Forward Secure Pseudorandom Numbers,” (now U.S. Pat. No. 9,008,303), incorporated by reference herein, discloses techniques for forward-secure generation of pseudorandom keys. The disclosed forward-secure pseudorandom generator (FS-PRNG) scheme allows for synchronous and asynchronous key updates, as well as event-driven and time-driven key updates. The disclosed key update procedure provides low catch-up costs while keeping the required storage requirements small.
When keys are generated using software, such as on a smartphone, the key update procedure is often based on the current time of the device used to compute the key (referred to as the device time). For example, to generate a new key (e.g., a passcode), the user typically launches a key update application (app) on the device and enters a personal identification number (PIN) to establish his or her identity. The key update application then determines the current device time, performs a “jump-ahead” operation using a key-update tree structure to catch-up to the current device time, and computes the new key for the current device time.
If the user is able to manipulate the device time, however, the key update application will compute the wrong key for the current actual time. When the device time is later in time than the current actual time (referred to herein as a forward clock attack), the user or attacker is able to obtain a key that will be valid for a later time. In addition, the internal state of the key-update tree is locked to the future device time. Accordingly, if the user later corrects the device time to the actual time, then the forward-secure key generation module becomes blocked/locked to a future time, and thus the system using the forward-secure keys may remain unusable for a certain amount of time (e.g., until the time corresponding to the forward clock attack point is reached). In general, the key generation module of the device will not be in synchronization with the corresponding server (that makes use of the produced keys) as the server (which is expected to accurately keep track of the actual time) will be in a state that corresponds to a future/forwarded point in time, and not with device time.
A need exists for pseudorandom generators (FS-PRNGs) that are forward secure as well as resilient to such forward clock attacks. Resilience, here, means that in the case of forward clock attacks, the system is able to (1) unblock the forward-secure key generation module, (2) detect a forward clock attack, (3) synchronize the module with the correct time used by the corresponding server that makes use of the keys (thus preventing Denial-of-Service attacks related to lack of synchronization), and (4) possibly even prevent the usage of the leaked-in-the-future key by an attacker.